package com.le.medium.class4;

import org.junit.Test;

/**
 * 给你一个二维数组matrix，其中每个数都是正数，要求从左上角走到右下角。
 * 每 一步只能向右或者向下，沿途经过的数字要累加起来。
 * 最后请返回最小的路径和
 */
public class Problem04_MinPathSum {

    public static int minPath1(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return -1;
        }

        return process(matrix, 0, 0);
    }

    // 暴力递归
    private static int process(int[][] matrix, int i, int j) {
        if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            return matrix[i][j];
        }

        // 最后一行,只能向右走
        if (i == matrix.length - 1) {
            return matrix[i][j] + process(matrix, i, j + 1);
        }
        // 最后一列，只能向左走
        if (j == matrix[0].length - 1) {
            return matrix[i][j] + process(matrix, i + 1, j);
        }
        // 一般情况
        return matrix[i][j] + Math.min(process(matrix, i + 1, j), process(matrix, i, j + 1));
    }

    // 动态规划
    public static int process2(int[][] matrix) {
        // dp表示，在i位置的最小路径和
        // 当前位置依赖 左边 和 上边 位置
        int[][] dp = new int[matrix.length][matrix[0].length];
        dp[0][0] = matrix[0][0];
        // 第一列位置可以确定
        for (int i = 1; i < matrix.length; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        // 第一行可以确定
        for (int i = 1; i < matrix[0].length; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }

        // 普遍位置，依赖上，左两个位置
        // 当前位置的值 加上 依赖位置的最小值，即使当前位置的最小路径和
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[matrix.length - 1][matrix[0].length - 1];
    }

    // 动态规划，空间压缩
    public static int process3(int[][] m) {
        int[] dp = new int[m[0].length];
        dp[0] = m[0][0];
        // 第一行确定
        for (int i = 1; i < dp.length; i++) {
            dp[i] = m[0][i] + dp[i - 1];
        }
        for (int i = 1; i < m.length; i++) {
            for (int j = 0; j < dp.length; j++) {
                dp[j] = j == 0 ? m[i][j] + dp[j] : m[i][j] + Math.min(dp[j - 1], dp[j]);
            }
        }
        return dp[m[0].length - 1];
    }

    @Test
    public void test() {
        int[][] arr = {
                {1, 3, 5, 9},
                {8, 1, 3, 4},
                {5, 0, 6, 1,},
                {8, 8, 4, 0}
        };
        System.out.println(minPath1(arr));
        System.out.println(process2(arr));
        System.out.println(process3(arr));
    }
}
